#include "StdAfx.h"
#include "ConstructionPhase.h"
#include "Dijkstra.h"

#include <algorithm>

Red * ConstructionPhase::ejecutar()
{
	InfoVertice s = selectRandomTerminal();
	set<int> terminalesAgregados; //Y
	set<int> terminalesFaltantes;
	initTerminalesFaltantes(terminalesFaltantes);

	Red * gSol = new Red(grafo->getCantidadNodos());
	agregarNuevoTerminal(gSol, s, terminalesAgregados, terminalesFaltantes);

	vector<HPath> rcl;

	while (terminalesAgregados.size() != grafo->getCantidadNodosTerminales()) {

		construirCaminosMasCortos(gSol, terminalesFaltantes, rcl);
		HPath hPath = selectRandomHPath(rcl);
		agregarCaminos(gSol, hPath);

		eliminarKeyPathRedundante(gSol, hPath);

		actualizarTerminalesAgregados(terminalesAgregados, terminalesFaltantes, hPath); //asumo terminal objetivo
																//contenido en caminos
	}

	return gSol;
}

InfoVertice ConstructionPhase::selectRandomTerminal()
{
	InfoVerticeSet &terminalesSet = grafo->getNodosTerminales();
	int eleccion = rand() % terminalesSet.size();
	InfoVerticeSet::const_iterator it(terminalesSet.begin());
	advance(it, eleccion);

	return *it;
}

void ConstructionPhase::initTerminalesFaltantes(set<int> &faltantes)
{
	InfoVerticeSet &terminales = grafo->getNodosTerminales();
	for (InfoVerticeSet::iterator it = terminales.begin(); it != terminales.end(); it++) {
		faltantes.insert(it->idVertice);
	}
}

void ConstructionPhase::agregarNuevoTerminal(Red * gSol, InfoVertice &s, set<int> &terminalesAgregados,
														 set<int> &terminalesFaltantes)
{
	gSol->agregarNodo(s);
	terminalesAgregados.insert(s.idVertice);
	terminalesFaltantes.erase(s.idVertice);
}

void ConstructionPhase::construirCaminosMasCortos(Red * gSol, set<int> &terminalesFaltantes, 
												  vector<HPath> &rcl)
{
	Path p1Temp;
	Path p2Temp;

	rcl.clear();
	//resize entre minimo de terminalesFaltantes y lSize
	int rclSize = (listSize < terminalesFaltantes.size()) ? listSize : terminalesFaltantes.size();
	rcl.resize(rclSize); //default constructor HPath con costo infinito!

	for (set<int>::iterator it = terminalesFaltantes.begin(); it != terminalesFaltantes.end(); it++) {

		construirKeyPathMinimo(gSol, InfoVertice(*it, true), p1Temp, p2Temp);
		double costoHPath = p1Temp.getCosto() + p2Temp.getCosto();
		if (costoHPath < rcl[rclSize-1].getCosto()) {
			rcl.pop_back();
			rcl.push_back(HPath(p1Temp, p2Temp, costoHPath));
			sort(rcl.begin(), rcl.end(), hpath_compare());
		}
	}
}

void ConstructionPhase::construirKeyPathMinimo(Red * gSol, InfoVertice & terminal, 
											   Path &p1, Path &p2)
{

	//desde terminalId hasta llegar a algun nodo perteneciente a gSol
	Dijkstra::ejecutar(gSol, terminal, p1, grafo, grafo->getCantidadNodos());
	
	Red * H = new Red(grafo); 
	InfoVerticeSet nodosSet;
	InfoArista aristaEliminar;
	obtenerNodosUsados(gSol, p1, nodosSet);
	if (gSol->getCantidadNodos() == 1) {
		//si es cicloInicial, quitar nodo final del camino del nodoSet
		nodosSet.erase(*(gSol->getNodos().begin()));
		
		if (p1.getPath().size() == 2) {
			//remover arista final (para el caso en que el camino inicial sea de terminal a terminal
			//y de largo 2... sino va a encontrar nuevamente el mismo camino el proximo dijkstra)
			aristaEliminar.vertices.first = p1.getPath()[0].idVertice;
			aristaEliminar.vertices.second = p1.getPath()[1].idVertice;
			aristaEliminar.costo = p1.getCosto();
			H->eliminarArista(aristaEliminar);
		}

	}
	
	H->removerNodos(nodosSet);
	Dijkstra::ejecutar(gSol, terminal, p2, H, grafo->getCantidadNodos());

	delete H;
}

void ConstructionPhase::obtenerNodosUsados(Red * gSol, Path &p, InfoVerticeSet& nodosUsados)
{
	//nodosUsados = gSol->getNodos(); //cuidado, referencia o copia?
	vector<InfoVertice> &path = p.getPath();
	for (int i=1; i<path.size(); i++) { //en el 0 esta el terminal objetivo, no se elimina del grafo
		nodosUsados.insert(grafo->getInfoVertice(path[i].idVertice));
	}
}

HPath ConstructionPhase::selectRandomHPath(vector<HPath> &rcl)
{
	int eleccion = rand() % rcl.size();
	HPath hPath = rcl[eleccion];
	return hPath;
}

void ConstructionPhase::agregarCaminos(Red * gSol, HPath &hPath)
{
	gSol->agregarKeyPath(hPath.getP1(), grafo);
	gSol->agregarKeyPath(hPath.getP2(), grafo);
}

void ConstructionPhase::eliminarKeyPathRedundante(Red * gSol, HPath &hPath)
{

}

void ConstructionPhase::actualizarTerminalesAgregados(set<int> &terminalesActuales, 
													  set<int> &terminalesFaltantes, HPath &hPath)
{
	vector<InfoVertice> &camino = hPath.getP1().getPath();
	for (int i=0; i<camino.size(); i++) {
		if (camino[i].esTerminal) {
			terminalesActuales.insert(camino[i].idVertice);
			terminalesFaltantes.erase(camino[i].idVertice);
		}
	}

	camino = hPath.getP2().getPath();
	for (int i=0; i<camino.size(); i++) {
		if (camino[i].esTerminal) {
			terminalesActuales.insert(camino[i].idVertice);
			terminalesFaltantes.erase(camino[i].idVertice);
		}
	}
}

ConstructionPhase::~ConstructionPhase(void)
{
}
